/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (head == NULL || head->next == NULL || k <= 1) {
            return head;
        }

        ListNode* pre = NULL;
        ListNode* nextHead = NULL;
        ListNode* cur = head;
        ListNode* tail = NULL;

        while (cur) {
            tail = cur;
            for (int i = 0; tail && i < k - 1; ++i) {
                tail = tail->next;
            }
            if (tail == NULL) {
                break;
            }
            // pre, [cur, tail], nextHead;
            nextHead = tail->next;
            ListNode *t0 = cur;
            ListNode *t1 = cur->next;
            ListNode *t2 = NULL;
            while (t0 != tail) {
                t2 = t1->next;
                t1->next = t0;
                t0 = t1;
                t1 = t2;
            }
            if (pre == NULL) {
                head = tail;
            } else {
                pre->next = tail;
            }
            cur->next = nextHead;

            pre = cur;
            cur = cur->next;
        }

        return head;
    }
};
